package com.wj.algorithm.lintcode;

import com.wj.algorithm.ArrayUtil;

public class P61 {
    public int[] searchRange1(int[] a, int target, int first, int last) {
        int[] nullResult = new int[]{-1, -1};
        
        return nullResult;
    }

    public int[] searchRangeFrom(int[] a, int index, int target) {
        int first = index;
        int tempIndex = index;
        tempIndex --;
        while(tempIndex >= 0) {
            if(a[tempIndex] == target) {
                first = tempIndex;
                tempIndex --;
            } else {
                break;
            }
        }
        int end = index;
        tempIndex = index;
        tempIndex ++;
        int len = a.length;
        while(tempIndex < len) {
            if(a[tempIndex] == target) {
                end = tempIndex;
                tempIndex ++;
            } else {
                break;
            }
        }
        
        return new int[]{first, end};
    }
    
    public int[] searchRange(int[] a, int target) {
        int[] nullResult = new int[]{-1, -1};
        if(a == null || a.length <= 0) {
            return nullResult;
        }
        int len = a.length;
        if(len == 1) {
            return a[0] == target ? new int[]{0 , 0} : nullResult;
        }
        
        int left = 0;
        int right = len - 1;
        int mid = (left + right + 1) / 2 ;
        
        while(mid >= left && mid <= right) {
            int lv = a[left];
            int mv = a[mid];
            int rv = a[right];
            
            if(target > rv || target < lv) {
                return nullResult;
            }
            if(right - left <= 2) {
                return searchRange1(a, target, left, right);
            }

            if(target > lv && target < mv) {
                //左边
                right = mid;
            } else if(target > mv && target < rv) {
                //右边
                left = mid;
            } else {
                if(lv == target) {
                    return searchRangeFrom(a, left, target);
                } else if(mv == target) {
                    return searchRangeFrom(a, mid, target);
                } else if(rv == target){
                    return searchRangeFrom(a, right, target);
                }
            }
            mid = (left + right + 1) / 2;
        }

        return nullResult;
    }
    
    public static void main(String[] args) {
        System.out.println(ArrayUtil.toString(new P61().searchRange(new int[]{1,10,1001,201,1001,10001,10007}, 10008)));
    }
}
